public class test_24_09_03 {


    //Definition for singly-linked list.
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public class Solution01 {
        // 使用快慢指针，类似于数学中的快慢追击问题
        public boolean hasCycle(ListNode head) {
            if (head == null || head.next == null)
                return false;
            ListNode slow = head;
            ListNode fast = head.next;
            while (slow != fast) {
                slow = slow.next;
                if (fast == null || fast.next == null)
                    return false;
                fast = fast.next.next;
            }
            return true;
        }
    }

    public class Solution02 {
        public ListNode detectCycle(ListNode head) {
            // 双指针
            // 返回入环第一个节点
            if (head == null || head.next == null)
                return null;
            ListNode slow = head, fast = head;
            while (true) {
                if (fast == null || fast.next == null)
                    return null;
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast)
                    break;
            }
            // 此时fast和slow已经在同一个节点了，并且都在环内
            // 如何寻找这个换的头节点呢？
            fast = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return fast;
        }
    }

    public class Solution03 {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode la = headA, lb = headB;
            while (la != lb) {
                la = la == null ? headB : la.next;
                lb = lb == null ? headA : lb.next;
            }
            return la;
        }
    }

    class Solution04 {
        public ListNode removeNthFromEnd(ListNode head, int n) {
            int count = 0;
            ListNode dummy = new ListNode(0, head);
            ListNode node = dummy;
            while (node.next != null) {
                node = node.next;
                count++;
            }
            node = dummy;
            for (int i = 0; i < count - n; i++) {
                node = node.next;
            }
            node.next = node.next.next;
            return dummy.next;
        }
    }


    class Solution05 {
        public ListNode reverseList(ListNode head) {
            ListNode cur = head;
            ListNode prev = null;
            while (cur != null) {
                ListNode curnext = cur.next;
                cur.next = prev;
                prev = cur;
                cur = curnext;
            }
            return prev;
        }
    }

    class Solution06 {
        public ListNode reverseList(ListNode head) {
            return reverse(head, null);
        }

        public ListNode reverse(ListNode cur, ListNode prev) {
            if (cur == null)
                return prev;
            ListNode curnext = cur.next;
            cur.next = prev;
            prev = cur;
            cur = curnext;
            return reverse(cur, prev);
        }
    }


}
